/**
 * @param {number[][]} points
 * @return {number}
 */
export var largestTriangleArea = function (points) {
  // 查出所有凸包点
  const hull = convexHull(points)
  if (hull.length < 3) {
    return 0
  }
  // 初始化最大面积
  let ans = 0
  // 对每个点，计算出三角形面积
  for (let i = 0; i < hull.length; i++) {
    for (let j = i + 1; j < hull.length; j++) {
      for (let k = j + 1; k < hull.length; k++) {
        ans = Math.max(ans, area(hull[i], hull[j], hull[k]))
      }
    }
  }
  return ans
}

/**
 * 两点之间的距离
 */
function distance(p1, p2) {
  return Math.sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2)
}

/**
  * 三角形面积公式
 已知三角形三边a,b,c，则
（海伦公式） p = (a+b+c)/2
  S=sqrt[p(p-a)(p-b)(p-c)]
  =sqrt[(1/16)(a+b+c)(a+b-c)(a+c-b)(b+c-a)]
  =1/4sqrt[(a+b+c)(a+b-c)(a+c-b)(b+c-a)]
 */
function area(p1, p2, p3) {
  const a = distance(p1, p2)
  const b = distance(p2, p3)
  const c = distance(p3, p1)
  const p = (a + b + c) / 2
  return Math.round(Math.sqrt(p * (p - a) * (p - b) * (p - c)))
}

/**
 * 凸包计算， 使用叉积法判断点三点是否在同一条直线
 * 负值表示顺时针，正值表示逆时针，0表示三点共线
 * @param {[number, number]} a
 * @param {[number, number]} b
 * @param {[number, number]} c
 * @returns {number}
 */
function cross(a, b, c) {
  return (b[0] - a[0]) * (c[1] - b[1]) - (b[1] - a[1]) * (c[0] - b[0])
}

// 查出所有凸包点
function convexHull(points) {
  // 先从左向右排序
  points.sort((a, b) => {
    if (a[0] - b[0] === 0) return a[1] - b[1]
    return a[0] - b[0]
  })

  const ans = [points[0], points[1]]
  // 先从左向右遍历，连结出下边的线
  for (let i = 2; i < points.length; i++) {
    while (ans.length >= 2 && cross(ans[ans.length - 2], ans[ans.length - 1], points[i]) < 0) {
      ans.pop()
    }
    ans.push(points[i])
  }
  // 从右向左再找一次，连结出上边的线
  for (let i = points.length - 2; i >= 0; i--) {
    while (ans.length >= 2 && cross(ans[ans.length - 2], ans[ans.length - 1], points[i]) < 0) {
      ans.pop()
    }
    ans.push(points[i])
  }
  ans.pop() // pop 出重复的起点
  return ans
}
